//
// Created by cheng on 2021/02/25.
//
#include "BiTree.h"


void PreOrder_Recursion(BinaryTree & t) {
    if (t != nullptr) {
        std::cout << t->key << " ";
        PreOrder_Recursion(t->lChild);
        PreOrder_Recursion(t->rChild);
    }
}

void InOrder_Recursion(BinaryTree& t) {
    if (t != nullptr) {
        InOrder_Recursion(t->lChild);
        std::cout << t->key << " ";
        InOrder_Recursion(t->rChild);
    }
}

void PostOrder_Recursion(BinaryTree& t) {
    if (t != nullptr) {
        PostOrder_Recursion(t->lChild);
        PostOrder_Recursion(t->rChild);
        std::cout << t->key << " ";
    }
}

void insert(int key, BinaryTree& tree) {
    // tree为空树，则直接插入结点
    if (tree == nullptr) {
        tree = new Node(key);
    } else { // 否则
        if (tree->key > key) {
            insert(key, tree->lChild);
        } else {
            insert(key, tree->rChild);
        }
    }
}

bool Find(int key, BinaryTree& tree) {
    if (tree == nullptr) {
        return false;
    }
    std::queue<BinaryTree> queue;
    queue.push(tree);
    while (!queue.empty()) {
        auto item = queue.front();
        queue.pop();
        if (item == nullptr) {
            continue;
        }
        if (item->key == key) {
            return true;
        } else {
            queue.push(item->lChild);
            queue.push(item->rChild);
        }
    }
    return false;
}

void Delete(BinaryTree &tree, Node *node) {
    Node *dNode, *nextNode, *childNode;
    // 如果同时存在左右子节点
    if (node->lChild != nullptr && node->rChild != nullptr) {
        // 获取删除节点的后继节点
        nextNode = getSuccessor(node);
        // 将后继节点的key转移
        node->key = nextNode->key;
        // 将要删除的结点设置为后继节点
        node = nextNode;
    }
    // 经过上一步的处理，可以确定node节点只能是有一个或者两个结点
    if (dNode->lChild != nullptr) {
        childNode = dNode->lChild;
    } else {
        childNode = dNode->rChild;
    }



}

Node *getSuccessor(Node *pNode) {
    return nullptr;
}
